package day23;

// 编辑距离 ：可以增加、删除、修改

import java.util.Scanner;


/* 整体错误！！
public class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            int count = 0;
            String a = in.nextLine();
            String b = in.nextLine();
            // a -> b 最少修改次数  （只操作a)
            // 如果后面一个相等就删除， 如果后面一个相等就增加，如果后面相等就修改这个
            for (int i = 0; i < a.length(); i++) {
                // 只是修改a
                if(a.charAt(i)==b.charAt(i)) {
                    continue;  // 下一个循环
                } else if(i+1<a.length() && a.charAt(i+1)==b.charAt(i)) {
                    // 删除
                    count++;
                } else if(a.charAt(i)==b.charAt(i+1)) {
                    // 增加
                    count++;
                } else if(i==a.length()-1 || i==b.length()-1) {
                    Math.abs(a.length()-b.length()-count);
                } else {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}*/



import java.util.*;

public class Main2{
    public static int getDistance(String str1,String str2){
        // 把字符串转为字符数组！！
        char[] arr1=str1.toCharArray();
        char[] arr2=str2.toCharArray();
        int l1=arr1.length;
        int l2=arr2.length;
        //定义一个矩阵：二维数组
        int[][]dist=new int[l1+1][l2+1];
        // 下标：0-l1/ 0-l2 ：多一行一列是为了有一行/列来存放下标
        //初始状态F（0，j）=j（插入）F（i，0）=i（删除）
        for(int i=0;i<=l1;i++){
            dist[i][0]=i;  // 第一列存下标
        }
        for(int j=0;j<=l2;j++){
            dist[0][j]=j;  // 第一行存下标
        }
        // 第0行/列被用于存放下标。那就从第一行/列开始！
        for(int i=1;i<=l1;i++){
            for(int j=1;j<=l2;j++){
                //F（i,j）=min{F(i,j-1)+1，F(i-1,j)+1，F(i-1,j-1)+(A[i]==B[j]?0:1)}
                dist[i][j]=Math.min(dist[i][j-1]+1,dist[i-1][j]+1);
                if(arr1[i-1]==arr2[j-1]){
                    dist[i][j]=Math.min(dist[i][j],dist[i-1][j-1]);
                }else{
                    dist[i][j]=Math.min(dist[i][j],dist[i-1][j-1]+1);
                }
            }
        }
        return dist[l1][l2];
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str1=scanner.nextLine();
            String str2=scanner.nextLine();
            int x=getDistance(str1,str2);
            System.out.println(x);
        }
    }
}

